package sun.scheduler.core;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.LinkedList;
import javax.xml.stream.events.EndDocument;
import sun.scheduler.core.ScheduleGraph.StartTimes;
import sun.scheduler.core.job.DummyJob;
import sun.scheduler.core.job.Process;
import sun.scheduler.core.job.Job;
import sun.scheduler.core.job.LTCTInfo;
import sun.scheduler.util.graph.BFSIterator;
import sun.scheduler.util.graph.Edge;
import sun.scheduler.util.graph.EdgeIterator;
import sun.scheduler.util.graph.Node;
import sun.scheduler.util.graph.algorithm.maxflow.*;

/**
 * Optimizes a given Project Plan represented by a PERT-diagram, asuming no
 * Resource boundries. The implemented Methods use the critical Path method and
 * Min-Cut computation, for finding the edges with an optimal cost rate.
 *
 *
 * @see ScheduleGraph
 * @see Schedule
 * @author mfj, May
 */
public class ScheduleOptimizer implements Iterator<ScheduleGraph>, Runnable
{

    /**
     * Precission used to compare values.
     */
    public final static double DEFAULT_PRECISION = 1e-4;
    /**
     *
     * Precission used to compare {@code double} values.
     */
    public final double precision;
    private ScheduleGraph sGraph;
    private ResidualGraph residualGraph;
    private State state;
    private int iteration = 0;
    private LinkedList<Node<StartTimes, Job>> cutSet;
    private long minDelta;
    private ArrayList<Edge<StartTimes, Job>> reduceable;
    private ArrayList<Edge<StartTimes, Job>> increasable;

    /**
     * Instantiatates a new {@link ScheduleOptimizer} from the given {@link ScheduleGraph}.
     *
     * @param sGraph
     */
    public ScheduleOptimizer(ScheduleGraph sGraph)
    {
        this(sGraph, DEFAULT_PRECISION);
    }

    /**
     * Instantiatates a new {@link ScheduleOptimizer} from the given {@link ScheduleGraph}.
     *
     * @param sGraph the PERT-diagram to optimize
     * @param precision the precision used for {@code double} value comparison.
     */
    public ScheduleOptimizer(ScheduleGraph sGraph, double precision)
    {
        this.sGraph = sGraph;
        this.state = State.Initialized;
        this.precision = precision;
    }

    /**
     * The current {@link State} of this Optimizer.
     *
     * @return the current state.
     */
    public State getState()
    {
        return state;
    }

    /**
     * Computes the Plan such that the time for completion is minimal. The used
     * on the other hand go up.
     */
    @Override
    public void run()
    {
        while (hasNext())
            next();
    }

    /**
     * Checks if the optimization process is completed, i.e. if there are still
     * edges left which duration can be reduced.
     *
     * @return {@code state != State.Finished}
     */
    @Override
    public boolean hasNext()
    {
        return state != State.Finished;
    }

    /**
     * Reduces the overall duration by changing the duration of the edges in the
     * critical network on the min-cut of the cost rates. If no further
     * optimization is possible the state is set to {@link State.Finished}
     * otherwise the state is set to {@link State.Running}.
     *
     * @return the {@link ScheduleGraph} to optimize.
     */
    @Override
    public ScheduleGraph next()
    {
        sGraph.setCurveState(Job.CurveState.LTCT);
        // init or update the residual graph
        switch (state)
        {
            case Initialized:
                state = State.Running;
                initializeResidualGraph();
                break;
            case Running:
                // TODO Fix update and replace this
                initializeResidualGraph();
                break;
            case Finished:
                return sGraph;
        }

        //rund edmont karp
        int sourceId = sGraph.getSourceId();
        int targetId = sGraph.getTargetId();
        while (residualGraph.augmentPath(sourceId, targetId));

        // reduce/increase time of edges
        minDelta = initializeReduction();

        for (Edge<StartTimes, Job> edge : reduceable)
        {
            LTCTInfo ltctInfo = (LTCTInfo) edge.getData().getProcess(Job.CurveState.LTCT);
            ltctInfo.increaseDuration(-minDelta);
        }
        for (Edge<StartTimes, Job> edge : increasable)
        {
            LTCTInfo ltctInfo = (LTCTInfo) edge.getData().getProcess(Job.CurveState.LTCT);
            ltctInfo.increaseDuration(minDelta);
        }

        // check if we are done
        if (reduceable.isEmpty() && increasable.isEmpty())
            state = State.Finished;

        iteration++;
        return sGraph;
    }

    private void initializeResidualGraph()
    {
        // setup residual graph with critical edges
        sGraph.updateJobTimeParameters();
        residualGraph = new ResidualGraph(sGraph, precision);

        EdgeIterator<StartTimes, Job> edgeIterator = sGraph.getEdgeIterator();
        while (edgeIterator.hasNext())
        {
            Edge<StartTimes, Job> next = edgeIterator.next();
            if (sGraph.isCritical(next))
                residualGraph.addEdge(next, (LTCTInfo) next.getData().getProcess(Job.CurveState.LTCT));
        }
    }

    private void updateResidualGraph()
    {
        // setup residual graph with critical edges
        sGraph.updateJobTimeParameters();

        EdgeIterator<StartTimes, Job> edgeIterator = sGraph.getEdgeIterator();
        while (edgeIterator.hasNext())
        {
            Edge<StartTimes, Job> next = edgeIterator.next();
            if (sGraph.isCritical(next))
                residualGraph.addEdge(next, (LTCTInfo) next.getData().getProcess(Job.CurveState.LTCT));
            else
                residualGraph.removeEdge(next.getStart().id(), next.getEnd().id());
        }
    }

    private boolean[] initializeCutset()
    {
        boolean[] isInCut = new boolean[residualGraph.getNumOfNodes()];

        // compute cutset in schedule graph and set map isCut
        cutSet = new LinkedList<Node<StartTimes, Job>>();
        BFSIterator<Label, ResidualEdgeData> iter = residualGraph.getBFSIterator(sGraph.getSourceId());
        while (iter.hasNext())
        {
            Node<Label, ResidualEdgeData> cutElem = iter.next();
            int cId = cutElem.id();
            cutSet.add(sGraph.getNode(cId));
            isInCut[cId] = true;
        }

        return isInCut;
    }

    private long initializeReduction()
    {
        boolean[] isInCut = initializeCutset();

        increasable = new ArrayList<Edge<StartTimes, Job>>();
        reduceable = new ArrayList<Edge<StartTimes, Job>>();

        long result = Long.MAX_VALUE;
        for (Node<StartTimes, Job> node : cutSet)
        {
            for (Edge<StartTimes, Job> edge : node.getOutEdges())
                if (!isInCut[edge.getEnd().id()])
                {
                    Job eData = edge.getData();
                    if (eData instanceof DummyJob)
                        continue;

                    // check if edge is critical
                    if (sGraph.isCritical(edge))
                    {
                        // duration reaches minimum
                        long delta = eData.getDuration(Job.CurveState.LTCT) - eData.minDuration;
                        if (delta == 0)
                        {
                            reduceable.clear();
                            return 0;
                        }

                        result = Math.min(result, delta);
                        reduceable.add(edge);

                    }
                    else
                        // edge (i,j) becomes critical: delta = j.LST - pij - i.EST 
                        result = Math.min(result, edge.getEnd().getData().getLatestStartTime()
                                - edge.getData().getDuration(Job.CurveState.LTCT) - edge.getStart().getData().getEarliestStartTime());

                }

            for (Edge<StartTimes, Job> edge : node.getInEdges())
                if (!isInCut[edge.getStart().id()])
                {
                    Job eData = edge.getData();
                    if (eData instanceof DummyJob)
                        continue;

                    // check if edge is critical
                    if (sGraph.isCritical(edge))
                    {
                        // duration reaches minimum
                        long delta = eData.maxDuration - eData.getDuration(Job.CurveState.LTCT);
                        if (delta == 0)
                        {
                            reduceable.clear();
                            increasable.clear();
                            return 0;
                        }

                        result = Math.min(result, delta);
                        increasable.add(edge);
                    }
                }
        }

        return result;
    }

    /**
     * Not supported.
     */
    @Override
    public void remove()
    {
        throw new UnsupportedOperationException("Not supported.");
    }

    /**
     * Prints the status of this instance.
     */
    public void printState()
    {
        System.out.println("[Iteration " + iteration + " - " + state + "]");
        System.out.println("Delta:              " + minDelta);
        System.out.println("Reduced Edges:      " + reduceable);
        System.out.println("Increased Edges:    " + increasable);
        System.out.println("Cutset:             " + cutSet);
    }

    /**
     * Possible states of the {@link ScheduleOptimizer}.
     */
    public enum State
    {
        Initialized, Running, Finished
    }
}